import random
from typing import List

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def quick_sort(l, r):
            if l >= r:
                return
            p = partition(l, r)
            quick_sort(l, p - 1)
            quick_sort(p + 1, r)

        def partition(l, r):
            # 随机选择pivot并交换到首位
            rand_idx = random.randint(l, r)
            nums[l], nums[rand_idx] = nums[rand_idx], nums[l]
            pivot = nums[l]
            
            # 双指针分区
            i, j = l + 1, r
            while True:
                while i <= j and nums[i] <= pivot:
                    i += 1
                while i <= j and nums[j] >= pivot:
                    j -= 1
                if i > j:
                    break
                nums[i], nums[j] = nums[j], nums[i]
            
            # 将pivot放到正确位置
            nums[l], nums[j] = nums[j], nums[l]
            return j

        quick_sort(0, len(nums) - 1)
        return nums